/**
 * @file traversal-tree.cpp
 * @author mixinju@outlook.com
 * @brief 二叉树的前中后和层序遍历
 * @version 0.1
 * @date 2021-11-25
 *
 * @copyright Copyright (c) 2021
 *
 */
#include <iostream>
#include <queue>
#include <vector>

#include "tree.h"
using namespace std;

/**
 * @brief 前序遍历的递归实现
 *
 * @param root
 * @param ans
 */
void preTraversal(TreeNode* root, vector<int>& ans) {
  if (root == nullptr) {
    return;
  }
  ans.emplace_back(root->val);
  preTraversal(root->left, ans);
  preTraversal(root->right, ans);

  return;
}

/**
 * @brief 中序遍历的递归实现
 *
 * @param root
 * @param ans
 */
void midTraversal(TreeNode* root, vector<int>& ans) {
  if (root == nullptr) {
    return;
  }

  midTraversal(root->left, ans);
  ans.emplace_back(root->val);
  midTraversal(root->right, ans);

  return;
}

/**
 * @brief 后序遍历的递归实现
 *
 * @param root
 * @param ans
 */
void backTraversal(TreeNode* root, vector<int>& ans) {
  if (root == nullptr) {
    return;
  }

  backTraversal(root->left, ans);
  backTraversal(root->right, ans);

  ans.emplace_back(root->val);
}

/**
 * @brief 二叉树的层序遍历-使用队列实现
 *
 * @param root
 * @param ans
 */
void layerTraversal(TreeNode* root, vector<int>& ans) {
  if (root == nullptr) {
    return;
  }

  queue<TreeNode*> Q;
  Q.push(root);
  ans.emplace_back(ans);

  while (!Q.empty()) {
    TreeNode* currNode = Q.front();
    Q.pop();

    int size = Q.size();
    for (int i = 0; i < size; ++i) {
      if (currNode->left) {
        Q.push(currNode->left);
        ans.emplace_back(currNode->left->val);
      }

      if (currNode->right->val) {
        Q.push(currNode->left);
        ans.emplace_back(currNode->left->val);
      }
    }
  }

  return;
}

/**
 * @brief 几种不同遍历的程序入口
 *
 * @param root
 * @return vector<int>
 */
vector<int> traversalTree(TreeNode* root) {
  if (root == nullptr) {
    return;
  }

  vector<int> ans;
  preTraversal(root, ans);
}